1. Field of the Invention
The invention relates in general to the field of cryptography, and more particularly to the field of protecting cryptographic calculations from being spied out. The invention relates especially to the transition between masked representations of a value, the masked representations being based on different masking rules. The invention is especially suited for use in a portable data carrier such as a smart card, for example, in different designs, or a chip module.
2. Description of Related Art
Encryption methods such as IDEA (International Data Encryption Algorithm), SAFER K-64 and RC5 as well as hash algorithms such as MD5 or SHA-1 execute cryptographic calculations in which payload data and key data are combined with one another by a series of different computing operations. Here, the computing operations XorL, AddM and MultM are frequently used. The operation XorL is the bitwise exclusive-or operation on L bits; this corresponds to the addition in (Z/2Z)L. The operation AddM is the addition modulo a modulus M ε Z, and the operation MultM is the multiplication modulo a modulus M ε Z. The cases L=8, 16, 32 are of particular importance for XorL, the cases M=28, 216, 232 are of particular importance for AddM, and the cases M=28+1, 216+1 are of particular importance for MultM.
Moreover, a modified multiplication is used in the IDEA method, wherein this modified multiplication is designated by the infix symbol {circle around (×)}. This IDEA multiplication is defined by d{circle around (×)}d′=I−1 (MultM (I(d), I(d′)) for d, d′ ε {0, . . . , 216−1}, the modulus M=216+1 and the following “I transformation”:
            I      ⁢              :            ⁢              {                  0          ,          …          ⁢                                          ,                                    2              16                        -            1                          }              ->          {              1        ,        …        ⁢                                  ,                  2          16                    }        ,          ⁢            I      ⁡              (        d        )              =          {                                                                                                                              2                      16                                                                                                            d                                                                                      if                                      ⁢                  {                                                                      d                  =                  0                                                                                                      d                  ≠                  0                                                                        
The IDEA multiplication has cryptographic advantages, because it ensures that the value zero is not contained in the data range of the multiplication MultM which is carried out, and moreover, because a prime number is used as the modulus M.
If computing operations such as the ones just mentioned are carried out using unprotected data, an inference can be made back to the operands and the result with the aid of SPA (Simple Power Analysis) or DPA (Differential Power Analysis). In this way, secret information or keys can be spied out. SPA and DPA methods are based on measuring power consumption whilst executing cryptographic calculations using a program-controlled device. In the case of an SPA attack, a single calculation run is analyzed. In a DPA attack, however, a plurality of calculation runs are statistically evaluated. In the choice of words of the present document, related attack methods in which, in addition to or instead of power consumption, at least one other physical parameter is measured, are also referred to as SPA or DPA methods, respectively.
As a measure against such attacks, the opportunity presents itself, to alter the data to be protected from being spied out by a value which, as a rule, is selected randomly. This value is known as a “mask”, and the computing algorithm, in accordance with which the data to be protected are processed together with the mask in order to obtain a masked representation of the data to be protected, is, in the present document, referred to as a “masking rule”. The cryptographic calculation steps are then carried out using the masked data. If an attacker manages to identify the values processed in the cryptographic calculation steps, then this spying-out relates only to masked representations and not to the data to be protected from being spied out.
The XorL masking rule and the AddM masking rule are frequently employed in veiling or disguising data. In the XorL masking rule, referred to also as “Boolean Masking”, the value d that is to be protected is represented by a masked representation y with the mask x, which is usually randomly selected, such that y=XorL(x, d) holds. In the AddM masking rule, referred to also as “Arithmetic Masking”, the value d to be protected is represented by a masked representation y with the mask x, which is usually randomly selected, such that 0≦x≦M−1 and y=AddM(x, d) hold. A minor modification of the AddM masking rule is the SubM masking rule, in which y=SubM(d, x) is chosen, wherein SubM(d, x) is the smallest non-negative number y for which AddM(x, y)=d holds.
It is understood that the respective masking rule that is used has to be compatible with the calculation step or the series of calculation steps to be performed. This is the case if, for example, the calculation step or the series of calculation steps, is/are also applicable, with at most minor modifications, to the masked representation of the value to be protected and then essentially result in the masked representation of the result desired. Hence, for example, the XorL masking rule is clearly compatible with exclusive-or calculation steps and bit permutations, however not with addition or multiplication operations.
However, in executing complex cryptographic methods, as cited in the introduction, series of calculation steps frequently alternate which are only compatible with different masking rules. Therefore, at the interface between such series of steps, a transition has to be effected between masked representations of a value to be protected which are based on different masking rules. The problem in this case is to design the masking rule transition, such that an attacker cannot obtain any usable information concerning the data to be protected.
Methods for the masking rule transition from a boolean to an arithmetic masking rule and vice versa are known from WO 02/51064 A1. In a first arrangement, a table is used therein, which table, for a fixed given mask, maps a masked representation in accordance with the first masking rule onto the corresponding masked representation in accordance with the second masking rule. In a second arrangement, such a table is applied to sections of values that have a larger bit length than the bit length of the table index. Furthermore, in this case, a carry table is employed.
The article “On Boolean and Arithmetic Masking against Differential Power Analysis” by J. S. Coron and L. Goubin, published in the conference proceedings of the “Workshop on Cryptographic Hardware and Embedded Systems 2000 (CHES 2000)”, vol. 1965 of “Lecture Notes in Computer Science”, Springer-Verlag, 2000, pp. 231-237, describes a method for the transition from a boolean to an arithmetic masking rule in which a mask, depending on a veiling parameter, enters into the course of calculation either complemented or non-complemented. In this article, reference is made to a possible DPA attack against this method.
From the article “A Sound Method for Switching between Boolean and Arithmetic Masking” by L. Goubin, published in the conference proceedings of the “Workshop on Cryptographic Hardware and Embedded Systems 2001 (CHES 2001)”, vol. 2162 of “Lecture Notes in Computer Science”, Springer-Verlag, 2001, pp. 3-15, calculation methods are known for the transition between boolean and arithmetic masking rules, which, in said article, are referred to as being secure from DPA attacks.
DE 198 22 217 A1 describes a method for protecting data from being spied out in which the masking is reverted before operations are carried out which are not compatible with the masking rule used.
The plurality of different information sources of which the attacker can potentially make use, is a particular difficulty in protecting the masking rule transition from being spied out. There is the problem that, during the course of the calculation, both the states of variables and the state changes of variables as well as the status bits of a processor, and the changes thereof, should be kept statistically independent from the data to be protected. In this respect, “status bits” refer to those processor register bits (flags) which indicate for example, a carry, or the occurrence of a negative number, or another property that is dependent on a calculation result. If merely one of these potential sources of information is not blocked, then there continues to be the risk of a successful DPA analysis.
The considerable resource restriction which is present, in particular, in smart cards and other portable data carriers, presents a further difficulty. It would be desirable to design the masking rule transition with regard to the necessary computing power as well as with regard to the memory space necessary for the program and for auxiliary data as efficiently as possible and as economical as possible in terms of storage, respectively.